package com.ashin.sort.insertion;

import org.junit.Test;

import java.util.Arrays;

/**
 * 插入排序
 *
 * @author Ashin
 */
public class InsertionSort {

    @Test
    public void sort(String[] args) {
        int[] sortedArray = {3, 2, 1, 8};

        insertionSort(sortedArray);

        System.out.print(Arrays.toString(sortedArray));
    }


    /**
     * 直接插入排序
     * 把n个元素的数列分成有序（前）和无序（后）的两部分<br/>
     * 每次处理就是将无序的数列中第一个元素与有序数列的元素从后到前比较，找到插入位置，将该元素插入到有序数列的适当的最终的位置上（稳定排序）。
     *
     * @param a
     */
    private void insertionSort(int[] a) {
        //将a[]按升序排列
        for (int i = 1; i < a.length; i++) {
            //将a[i]插入到a[i-1]，a[i-2]，a[i-3]……之中
            for (int j = i; j > 0 && (a[j - 1] > a[j]); j--) {
                int temp = a[j];

                a[j] = a[j - 1];

                a[j - 1] = temp;
            }
        }
    }
}
